{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Unguarded Cells in the Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countUnguarded"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计网格图中没有被保卫的格子数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>m</code>&nbsp;和&nbsp;<code>n</code>&nbsp;表示一个下标从<strong>&nbsp;0</strong>&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;网格图。同时给你两个二维整数数组&nbsp;<code>guards</code> 和&nbsp;<code>walls</code>&nbsp;，其中&nbsp;<code>guards[i] = [row<sub>i</sub>, col<sub>i</sub>]</code>&nbsp;且&nbsp;<code>walls[j] = [row<sub>j</sub>, col<sub>j</sub>]</code>&nbsp;，分别表示第 <code>i</code>&nbsp;个警卫和第 <code>j</code>&nbsp;座墙所在的位置。</p>\n",
    "\n",
    "<p>一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 <strong>所有</strong>&nbsp;格子，除非他们被一座墙或者另外一个警卫 <strong>挡住</strong>&nbsp;了视线。如果一个格子能被 <strong>至少</strong>&nbsp;一个警卫看到，那么我们说这个格子被 <strong>保卫</strong>&nbsp;了。</p>\n",
    "\n",
    "<p>请你返回空格子中，有多少个格子是 <strong>没被保卫</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/10/example1drawio2.png\" style=\"width: 300px; height: 204px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。\n",
    "总共有 7 个没有被保卫的格子，所以我们返回 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/10/example2drawio.png\" style=\"width: 200px; height: 201px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>上图中，没有被保卫的格子用绿色表示。\n",
    "总共有 4 个没有被保卫的格子，所以我们返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= guards.length, walls.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>2 &lt;= guards.length + walls.length &lt;= m * n</code></li>\n",
    "\t<li><code>guards[i].length == walls[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= row<sub>i</sub>, row<sub>j</sub> &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= col<sub>i</sub>, col<sub>j</sub> &lt; n</code></li>\n",
    "\t<li><code>guards</code>&nbsp;和&nbsp;<code>walls</code>&nbsp;中所有位置 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-unguarded-cells-in-the-grid](https://leetcode.cn/problems/count-unguarded-cells-in-the-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-unguarded-cells-in-the-grid](https://leetcode.cn/problems/count-unguarded-cells-in-the-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n6\\n[[0,0],[1,1],[2,3]]\\n[[0,1],[2,2],[1,4]]', '3\\n3\\n[[1,1]]\\n[[0,1],[1,0],[2,1],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid =[[1]*n for _ in range(m)]\n",
    "        \n",
    "        for wall in walls:\n",
    "            x,y = wall\n",
    "            grid[x][y] = False\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            grid[x][y] = False\n",
    "\n",
    "\n",
    "        def check_view(gd):\n",
    "            # up\n",
    "            x0, y0 = gd\n",
    "            for x in range(x0-1, -1, -1):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # down\n",
    "            for x in range(x0+1, m):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            # left\n",
    "            for y in range(y0-1, -1, -1):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # right\n",
    "            for y in range(y0+1, n):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            check_view(gd)\n",
    "        return sum([sum(x) for x in grid])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        unguard = 0\n",
    "\n",
    "        def cell_guarded(m,n):\n",
    "            for gd in guards:\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for m in range(m):\n",
    "            for n in range(n):\n",
    "                if not cell_guarded(m,n):\n",
    "                    unguard += 1\n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        grid =[[1]*n for _ in range(m)]\n",
    "        \n",
    "        for wall in walls:\n",
    "            x,y = wall\n",
    "            grid[x][y] = False\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            grid[x][y] = False\n",
    "\n",
    "\n",
    "        def check_view(gd):\n",
    "            # up\n",
    "            x0, y0 = gd\n",
    "            for x in range(x0-1, -1, -1):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # down\n",
    "            for x in range(x0+1, m):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            # left\n",
    "            for y in range(y0-1, -1, -1):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # right\n",
    "            for y in range(y0+1, n):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            check_view(gd)\n",
    "        return sum([sum(x) for x in grid])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        g = [[0] * n for _ in range(m)]\n",
    "        for x, y in guards:\n",
    "            g[x][y] = 1\n",
    "        for x, y in walls:\n",
    "            g[x][y] = 2\n",
    "\n",
    "        for i in range(m):\n",
    "            pre = -1\n",
    "            flag = False\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                if g[i][j] == 1:\n",
    "                    if flag == False:\n",
    "                        for jj in range(pre + 1, j):\n",
    "                            g[i][jj] = 3\n",
    "                    flag = True\n",
    "                elif g[i][j] == 2:\n",
    "                    flag = False\n",
    "                    pre = j\n",
    "                elif flag == True:\n",
    "                    g[i][j] = 3\n",
    "                j += 1\n",
    "\n",
    "        for j in range(n):\n",
    "            pre = -1\n",
    "            flag = False\n",
    "            i = 0\n",
    "            while i < m:\n",
    "                if g[i][j] == 1:\n",
    "                    if flag == False:\n",
    "                        for ii in range(pre + 1, i):\n",
    "                            g[ii][j] = 3\n",
    "                    flag = True\n",
    "                elif g[i][j] == 2:\n",
    "                    flag = False\n",
    "                    pre = i\n",
    "                elif flag == True:\n",
    "                    g[i][j] = 3\n",
    "                i += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j] == 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        for r,c in guards:\n",
    "            grid[r][c] = 1\n",
    "        for r,c in walls:\n",
    "            grid[r][c] = -1\n",
    "        \n",
    "\n",
    "        for i,(r,c) in enumerate(guards):\n",
    "            nr = r\n",
    "            while nr-1>=0 and grid[nr-1][c]!=1 and grid[nr-1][c]!=-1:\n",
    "                nr -= 1\n",
    "                grid[nr][c] = 2\n",
    "            nr = r\n",
    "            while nr+1<m and grid[nr+1][c]!=1 and grid[nr+1][c]!=-1:\n",
    "                nr += 1\n",
    "                grid[nr][c] = 2\n",
    "            nc = c\n",
    "            while nc-1>=0 and grid[r][nc-1]!=1 and grid[r][nc-1]!=-1:\n",
    "                nc -= 1\n",
    "                grid[r][nc] = 2\n",
    "            nc = c\n",
    "            while nc+1<n and grid[r][nc+1]!=1 and grid[r][nc+1]!=-1:\n",
    "                nc += 1\n",
    "                grid[r][nc] = 2\n",
    "            pass\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "\n",
    "        # Mark walls on the grid\n",
    "        for wall in walls:\n",
    "            grid[wall[0]][wall[1]] = -1\n",
    "\n",
    "        # Mark guards on the grid\n",
    "        for guard in guards:\n",
    "            grid[guard[0]][guard[1]] = 1\n",
    "\n",
    "        # Check for guarded cells in four cardinal directions\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        for guard in guards:\n",
    "            for dx, dy in directions:\n",
    "                x, y = guard[0] + dx, guard[1] + dy\n",
    "                while 0 <= x < m and 0 <= y < n and grid[x][y] != -1 and grid[x][y] != 1:\n",
    "                    if grid[x][y] == 0:\n",
    "                        grid[x][y] = 2\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "\n",
    "        # Count unguarded cells\n",
    "        unguarded_count = 0\n",
    "        for row in grid:\n",
    "            unguarded_count += row.count(0)\n",
    "\n",
    "        return unguarded_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        \n",
    "        vis=[[0]*n for _ in range(m)]\n",
    "        for x,y in guards:\n",
    "            vis[x][y]=1\n",
    "        for x,y in walls:\n",
    "            vis[x][y]=2\n",
    "\n",
    "        for x,y in guards:\n",
    "            x1,x2,x3,x4=x,x,x,x\n",
    "            y1,y2,y3,y4=y,y,y,y\n",
    "            while y1+1<n and vis[x1][y1+1]!=2 and vis[x1][y1+1]!=1:\n",
    "                y1=y1+1\n",
    "                vis[x1][y1]=3\n",
    "            while y2-1>=0 and vis[x2][y2-1]!=2 and vis[x2][y2-1]!=1:\n",
    "                y2=y2-1\n",
    "                vis[x2][y2]=3\n",
    "            while x3+1<m and vis[x3+1][y3]!=2 and vis[x3+1][y3]!=1:\n",
    "                x3=x3+1\n",
    "                vis[x3][y3]=3\n",
    "            while x4-1>=0 and vis[x4-1][y4]!=2 and vis[x4-1][y4]!=1:\n",
    "                x4=x4-1\n",
    "                vis[x4][y4]=3 \n",
    "        cnt=0        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j]==0:\n",
    "                    cnt+=1\n",
    "        \n",
    "\n",
    "        return cnt  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        mm = [[0] * n for _ in range(m)]\n",
    "        left = m * n - len(guards) - len(walls)\n",
    "        for x, y in guards + walls:\n",
    "            mm[x][y] = 1\n",
    "        \n",
    "        # def next_iter(row, col):\n",
    "        #     for xx, yy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "        #         nx = row + xx\n",
    "        #         ny = col + yy\n",
    "        #         if 0 <= nx < m and 0 <= ny < n:\n",
    "        #             yield nx, ny\n",
    "        for x, y in guards:\n",
    "\n",
    "            for xx, yy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                nx, ny = x + xx, y + yy\n",
    "                while 0 <= nx < m and 0 <= ny < n:\n",
    "                    if mm[nx][ny] == 0:\n",
    "                        left -= 1\n",
    "                        mm[nx][ny] = 2\n",
    "                        # print(nx, ny)\n",
    "                        nx += xx\n",
    "                        ny += yy\n",
    "                    elif mm[nx][ny] == 2:\n",
    "                        nx += xx\n",
    "                        ny += yy\n",
    "                    else:\n",
    "                        break\n",
    "        return left\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.meshgrid = []\n",
    "\n",
    "    def countUnguarded(self, m, n, guards, walls) -> int:\n",
    "        for _ in range(m):\n",
    "            self.meshgrid.append([0] * n)\n",
    "\n",
    "        # 开始在网格上染色，guard=6，wall=9，guarded=1，unguarded=0\n",
    "        for guard in guards:\n",
    "            self.meshgrid[guard[0]][guard[1]] = 6\n",
    "\n",
    "        for wall in walls:\n",
    "            self.meshgrid[wall[0]][wall[1]] = 9\n",
    "\n",
    "        # 遍历每个guard能守卫到的格子并染色\n",
    "        for guard in guards:\n",
    "            for i in range(guard[0] + 1):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if self.meshgrid[guard[0] - i][guard[1]] == 0:\n",
    "                    self.meshgrid[guard[0] - i][guard[1]] = 1\n",
    "                if (\n",
    "                    self.meshgrid[guard[0] - i][guard[1]] == 6\n",
    "                    or self.meshgrid[guard[0] - i][guard[1]] == 9\n",
    "                ):\n",
    "                    break\n",
    "            for i in range(m - guard[0]):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if self.meshgrid[guard[0] + i][guard[1]] == 0:\n",
    "                    self.meshgrid[guard[0] + i][guard[1]] = 1\n",
    "                if (\n",
    "                    self.meshgrid[guard[0] + i][guard[1]] == 6\n",
    "                    or self.meshgrid[guard[0] + i][guard[1]] == 9\n",
    "                ):\n",
    "                    break\n",
    "            for i in range(guard[1] + 1):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if self.meshgrid[guard[0]][guard[1] - i] == 0:\n",
    "                    self.meshgrid[guard[0]][guard[1] - i] = 1\n",
    "                if (\n",
    "                    self.meshgrid[guard[0]][guard[1] - i] == 6\n",
    "                    or self.meshgrid[guard[0]][guard[1] - i] == 9\n",
    "                ):\n",
    "                    break\n",
    "            for i in range(n - guard[1]):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if self.meshgrid[guard[0]][guard[1] + i] == 0:\n",
    "                    self.meshgrid[guard[0]][guard[1] + i] = 1\n",
    "                if (\n",
    "                    self.meshgrid[guard[0]][guard[1] + i] == 6\n",
    "                    or self.meshgrid[guard[0]][guard[1] + i] == 9\n",
    "                ):\n",
    "                    break\n",
    "\n",
    "        counter = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.meshgrid[i][j] == 0:\n",
    "                    counter += 1\n",
    "\n",
    "        return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        visit = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        res = m * n - len(guards) - len(walls)\n",
    "        \n",
    "        for g in guards:\n",
    "            visit[g[0]][g[1]] = -1\n",
    "        for w in walls:\n",
    "            visit[w[0]][w[1]] = -1\n",
    "\n",
    "        for g in guards:\n",
    "            row = g[0]\n",
    "            col = g[1] - 1\n",
    "            while col >= 0:\n",
    "                if visit[row][col] < 0:\n",
    "                    break\n",
    "                if visit[row][col] == 0:\n",
    "                    res -= 1\n",
    "                    visit[row][col] = 1\n",
    "                col -= 1\n",
    "            \n",
    "            row = g[0]\n",
    "            col = g[1] + 1\n",
    "            while col < n:\n",
    "                if visit[row][col] < 0:\n",
    "                    break\n",
    "                if visit[row][col] == 0:\n",
    "                    res -= 1\n",
    "                    visit[row][col] = 1\n",
    "                col += 1\n",
    "\n",
    "            row = g[0] - 1\n",
    "            col = g[1]\n",
    "            while row >= 0:\n",
    "                if visit[row][col] < 0:\n",
    "                    break\n",
    "                if visit[row][col] == 0:\n",
    "                    res -= 1\n",
    "                    visit[row][col] = 1\n",
    "                row -= 1\n",
    "\n",
    "            row = g[0] + 1\n",
    "            col = g[1]\n",
    "            while row < m:\n",
    "                if visit[row][col] < 0:\n",
    "                    break\n",
    "                if visit[row][col] == 0:\n",
    "                    res -= 1\n",
    "                    visit[row][col] = 1\n",
    "                row += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        # 初始化\n",
    "        for i, j in guards:\n",
    "            mat[i][j] = -1\n",
    "        for i, j in walls:\n",
    "            mat[i][j] = -1\n",
    "        for i, j in guards:\n",
    "            i_1, j_1 = i, j\n",
    "            while i_1 >= 1 and mat[i_1 - 1][j_1] != -1:\n",
    "                mat[i_1 - 1][j_1] = 1\n",
    "                i_1 -= 1\n",
    "            i_2, j_2 = i, j\n",
    "            while j_2 >= 1 and mat[i_2][j_2 - 1] !=-1:\n",
    "                mat[i_2][j_2 - 1] = 1\n",
    "                j_2 -= 1\n",
    "            i_3, j_3 = i, j\n",
    "            while i_3 < len(mat) - 1 and mat[i_3 + 1][j_3] != -1:\n",
    "                mat[i_3 + 1][j_3] = 1\n",
    "                i_3 += 1\n",
    "            i_4, j_4 = i, j\n",
    "            while j_4 < len(mat[0]) - 1 and mat[i_4][j_4 + 1] != -1:\n",
    "                mat[i_4][j_4 + 1] = 1\n",
    "                j_4 += 1\n",
    "        return m * n - (sum(element for row in mat for element in row) + 2 * len(guards) + 2 * len(walls))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        matrix = [[1] * n for _ in range(m)]\n",
    "        for i, j in guards:\n",
    "            matrix[i][j] = \"G\"\n",
    "        for i, j in walls:\n",
    "            matrix[i][j] = \"W\"\n",
    "        for i, j in guards:\n",
    "            for di, dj in (0, 1), (0, -1), (1, 0), (-1, 0):\n",
    "                cnt = 1\n",
    "                ni, nj = i + di * cnt, j + dj * cnt\n",
    "                while 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] in (0, 1):\n",
    "                    matrix[ni][nj] = 0\n",
    "                    cnt += 1\n",
    "                    ni, nj = i + di * cnt, j + dj * cnt\n",
    "        return sum(1 for i in range(m) for j in range(n) if matrix[i][j] == 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        \n",
    "        g=[['.']*n for _ in range(m)]\n",
    "        for x,y in walls:\n",
    "            g[x][y]='w'\n",
    "        \n",
    "        dirs={'>':(0,1),'<':(0,-1),'^':(-1,0),'v':(1,0)}\n",
    "        # obtacels={'#','<','>','^','v'}\n",
    "        # for i,row in enumerate(g):\n",
    "        #     for j,w in enumerate(row):\n",
    "        for i,j in guards:\n",
    "            g[i][j]='g'\n",
    "        for i,j in guards:\n",
    "            for dx,dy in dirs.values():\n",
    "            # elif w in dirs.keys():\n",
    "                # dx,dy=dirs[w]\n",
    "                \n",
    "                a,b=i+dx,j+dy\n",
    "                while 0<=a<m and 0<=b<n and (g[a][b]=='.' or g[a][b]=='!'):\n",
    "                    g[a][b]='!'\n",
    "                    a+=dx\n",
    "                    b+=dy\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j]=='.':\n",
    "                    ans+=1\n",
    "        # for row in g:\n",
    "        #     print(*row)\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        unguard = 0\n",
    "\n",
    "        def cell_guarded(m,n):\n",
    "            for gd in guards:\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for m in range(m):\n",
    "            for n in range(n):\n",
    "                if not cell_guarded(m,n):\n",
    "                    unguard += 1\n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        grid =[[1]*n for _ in range(m)]\n",
    "        \n",
    "        for wall in walls:\n",
    "            x,y = wall\n",
    "            grid[x][y] = False\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            grid[x][y] = False\n",
    "\n",
    "\n",
    "        def check_view(gd):\n",
    "            # up\n",
    "            x0, y0 = gd\n",
    "            for x in range(x0-1, -1, -1):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # down\n",
    "            for x in range(x0+1, m):\n",
    "                if grid[x][y0] is not False:\n",
    "                    grid[x][y0] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            # left\n",
    "            for y in range(y0-1, -1, -1):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "            # right\n",
    "            for y in range(y0+1, n):\n",
    "                if grid[x0][y] is not False:\n",
    "                    grid[x0][y] = 0\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        for gd in guards:\n",
    "            x,y = gd\n",
    "            check_view(gd)\n",
    "        print(grid)\n",
    "        return sum([sum(x) for x in grid])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        ans = m * n\n",
    "        wall = set()\n",
    "        guard = set()\n",
    "        w = g = 0\n",
    "        for x, y in walls:\n",
    "            wall.add((x, y))\n",
    "            w += 1\n",
    "        for x, y in guards:\n",
    "            guard.add((x, y))\n",
    "            g += 1\n",
    "        vis = set()\n",
    "        for R, C in guards:\n",
    "            for i in range(C + 1, n):\n",
    "                if (R, i) not in wall and (R, i) not in guard and (R, i) not in vis:\n",
    "                    ans -= 1\n",
    "                    vis.add((R, i))\n",
    "                elif (R, i) in wall or (R, i) in guard:\n",
    "                    break\n",
    "            for i in range(R - 1, -1, -1):\n",
    "                if (i, C) not in wall and (i, C) not in guard and (i, C) not in vis:\n",
    "                    ans -= 1\n",
    "                    vis.add((i, C))\n",
    "                elif (i, C) in wall or (i, C) in guard:\n",
    "                    break\n",
    "            for i in range(C - 1, -1, -1):\n",
    "                if (R, i) not in wall and (R, i) not in guard and (R, i) not in vis:\n",
    "                    ans -= 1\n",
    "                    vis.add((R, i))\n",
    "                elif (R, i) in wall or (R, i) in guard:\n",
    "                    break\n",
    "            for i in range(R + 1, m):\n",
    "                if (i, C) not in wall and (i, C) not in guard and (i, C) not in vis:\n",
    "                    ans -= 1\n",
    "                    vis.add((i, C))\n",
    "                elif (i, C) in wall or (i, C) in guard:\n",
    "                    break\n",
    "        return ans - w - g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for i, j in guards + walls:\n",
    "            f[i][j] = 1\n",
    "        visited = set()\n",
    "        for i, j in guards:\n",
    "            # 上\n",
    "            x, y = i - 1, j\n",
    "            while x >= 0:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    x = -1\n",
    "            # 下\n",
    "            x, y = i + 1, j\n",
    "            while x < m:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    x += 1\n",
    "                else:\n",
    "                    x = m\n",
    "            # 左\n",
    "            x, y = i, j - 1\n",
    "            while y >= 0:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    y -= 1\n",
    "                else:\n",
    "                    y = -1\n",
    "            # 右\n",
    "            x, y = i, j + 1\n",
    "            while y < n:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    y += 1\n",
    "                else:\n",
    "                    y = n\n",
    "        \n",
    "        return m * n - len(walls) - len(guards) - len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        st = set((x,y) for x, y in walls)\n",
    "        stg = set((x, y) for x, y in guards)\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        cnt = 0\n",
    "        for i, j in guards:\n",
    "            for dx, dy in (0,1),(1,0),(0,-1),(-1,0):\n",
    "                x, y = i, j\n",
    "                while 0 <= x + dx < m and 0 <= y + dy < n and (x+dx,y+dy) not in stg and (x+dx, y + dy) not in st:\n",
    "                    #print(f'{x+dx},{y+dy}')\n",
    "                    if vis[x + dx][y + dy] == 0:\n",
    "                        cnt += 1\n",
    "                    vis[x + dx][y + dy] = 1\n",
    "                    x, y = x + dx, y + dy\n",
    "        return m * n - cnt - len(guards) - len(walls)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for i, j in guards + walls:\n",
    "            f[i][j] = 1\n",
    "        visited = set()\n",
    "        for i, j in guards:\n",
    "            # 上\n",
    "            x, y = i - 1, j\n",
    "            while x >= 0:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    x = -1\n",
    "            # 下\n",
    "            x, y = i + 1, j\n",
    "            while x < m:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    x += 1\n",
    "                else:\n",
    "                    x = m\n",
    "            # 左\n",
    "            x, y = i, j - 1\n",
    "            while y >= 0:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    y -= 1\n",
    "                else:\n",
    "                    y = -1\n",
    "            # 右\n",
    "            x, y = i, j + 1\n",
    "            while y < n:\n",
    "                if f[x][y] == 0:\n",
    "                    visited.add((x, y))\n",
    "                    y += 1\n",
    "                else:\n",
    "                    y = n\n",
    "        \n",
    "        return m * n - len(walls) - len(guards) - len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        guards = set([tuple(x) for x in guards])\n",
    "        walls = set([tuple(x) for x in walls])\n",
    "        vis: List[List[bool]] = [[False] * n for _ in range(m)] \n",
    "\n",
    "        def check(i, j):\n",
    "            for k in range(i-1, -1, -1):\n",
    "                if (k, j) in walls or (k, j) in guards:\n",
    "                    break\n",
    "                vis[k][j] = True\n",
    "            for k in range(i+1, m):\n",
    "                if (k, j) in walls or (k, j) in guards:\n",
    "                    break\n",
    "                vis[k][j] = True\n",
    "            for k in range(j-1, -1, -1):\n",
    "                if (i, k) in walls or (i, k) in guards:\n",
    "                    break\n",
    "                vis[i][k] = True\n",
    "            for k in range(j+1, n):\n",
    "                if (i, k) in walls or (i, k) in guards:\n",
    "                    break\n",
    "                vis[i][k] = True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) in guards:\n",
    "                    vis[i][j] = True\n",
    "                    check(i, j)\n",
    "                if (i, j) in walls:\n",
    "                    vis[i][j] = True\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vis[i][j]:\n",
    "                    count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        vis = set()\n",
    "        grid = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for a, b in guards:\n",
    "            grid[a][b] = 'G'\n",
    "        for a, b in walls:\n",
    "            grid[a][b] = 'W'\n",
    "        nextMove = [(1,0), (0,1), (-1,0), (0,-1)]\n",
    "        for x, y in guards:\n",
    "            for i, j in nextMove:\n",
    "                new_x, new_y = x+i, y+j\n",
    "                while 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 0:\n",
    "                    vis.add((new_x,new_y))\n",
    "                    new_x,new_y = new_x+i,new_y+j\n",
    "        return m * n - len(vis) - len(guards) - len(walls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        visited_space = [[False] * n for _ in range(m)]\n",
    "        # 网格初始化\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        for guard in guards:\n",
    "            grid[guard[0]][guard[1]] = 1\n",
    "        for wall in walls:\n",
    "            grid[wall[0]][wall[1]] = 2\n",
    "        # 遍历每一个未处理的空白元素\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 从守卫开始沿4个方法\n",
    "                    for h in range(j + 1, n):\n",
    "                        if grid[i][h] == 0:\n",
    "                            visited_space[i][h] = True\n",
    "                        else:\n",
    "                            break\n",
    "                    for h in range(j - 1, -1, -1):\n",
    "                        if grid[i][h] == 0:\n",
    "                            visited_space[i][h] = True\n",
    "                        else:\n",
    "                            break\n",
    "                    for k in range(i - 1, -1, -1):\n",
    "                        if grid[k][j] == 0:\n",
    "                            visited_space[k][j] = True\n",
    "                        else:\n",
    "                            break\n",
    "                    for k in range(i + 1, m):\n",
    "                        if grid[k][j] == 0:\n",
    "                            visited_space[k][j] = True\n",
    "                        else:\n",
    "                            break\n",
    "        guard_count = sum(1 for i in range(m) for j in range(n) if visited_space[i][j])\n",
    "        return m * n - len(guards) - len(walls) - guard_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        vst = [[0] * n for _ in range(m)]\n",
    "        ret = m * n - len(guards) - len(walls)\n",
    "        grid = [[0] * n for i in range(m)]\n",
    "        dirs = ((-1, 0), (0, -1), (1, 0), (0, 1))\n",
    "        \n",
    "        for i, j in guards:\n",
    "            grid[i][j] = 1\n",
    "        \n",
    "        for i, j in walls:\n",
    "            grid[i][j] = 2\n",
    "        \n",
    "        \n",
    "        for i in range(m):\n",
    "            left = -1\n",
    "            flag = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for k in range(left + 1, j):\n",
    "                        vst[i][k] = 1\n",
    "                    left = j\n",
    "                    flag = 1\n",
    "                elif grid[i][j] == 2:\n",
    "                    if flag:\n",
    "                        for k in range(left + 1, j):\n",
    "                            vst[i][k] = 1\n",
    "                    left = j\n",
    "                    flag = 0\n",
    "            if flag:\n",
    "                for k in range(left + 1, n):\n",
    "                    vst[i][k] = 1\n",
    "            \n",
    "        for j in range(n):          \n",
    "            up = -1\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    for k in range(up + 1, i):\n",
    "                        vst[k][j] = 1\n",
    "                    flag = 1\n",
    "                    up = i\n",
    "                elif grid[i][j] == 2:\n",
    "                    if flag:\n",
    "                        for k in range(up + 1, i):\n",
    "                            vst[k][j] = 1\n",
    "                    up = i\n",
    "                    flag = 0\n",
    "            if flag:\n",
    "                for k in range(up + 1, m):\n",
    "                    vst[k][j] = 1\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cnt += vst[i][j]\n",
    "        return ret - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        ans = m * n\n",
    "        walls_ = set([])\n",
    "        for wall in walls:\n",
    "            tmp = (wall[0], wall[1])\n",
    "            walls_.add(tmp)\n",
    "        for guard in guards:\n",
    "            tmp = (guard[0], guard[1])\n",
    "            walls_.add(tmp)\n",
    "\n",
    "        visited = set([])\n",
    "        def bfs(x, y):\n",
    "            block = [0] * 4\n",
    "            directions = [[0,1],[0, -1], [1, 0], [-1, 0]]\n",
    "            for dir in directions:\n",
    "                _x = x + dir[0]\n",
    "                _y = y + dir[1]\n",
    "                while _x > -1 and _x < m and _y > -1 and _y < n:\n",
    "                    tmp = (_x, _y)\n",
    "                    if tmp not in walls_:\n",
    "                        nonlocal visited\n",
    "                        if tmp not in visited: \n",
    "                            visited.add(tmp)\n",
    "                    else:\n",
    "                        break\n",
    "                    _x += dir[0]\n",
    "                    _y += dir[1]\n",
    "        for guard in guards:\n",
    "            bfs(guard[0], guard[1])\n",
    "        #print(visited)\n",
    "        ans -= len(walls)\n",
    "        ans -= len(guards)\n",
    "        ans -= len(visited)\n",
    "        return ans\n",
    "\n",
    "                        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        safe = set()\n",
    "        s = set([tuple(guard) for guard in guards])\n",
    "        s = s.union(set([tuple(wall) for wall in walls]))\n",
    "\n",
    "        def mark(guard):\n",
    "            y, x = guard\n",
    "            dire = [(1, 0), (-1, 0), (0, 1), (0, - 1)]\n",
    "            for d in dire:\n",
    "                j = 1\n",
    "                while 0 <= y + d[0] * j < m and 0 <= x + d[1] * j < n and (y + d[0] * j, x + d[1] * j) not in s:\n",
    "                    safe.add((y + d[0] * j, x + d[1] * j))\n",
    "                    j += 1\n",
    "\n",
    "        for guard in guards:\n",
    "            mark(guard)\n",
    "\n",
    "        return m * n - len(safe) - len(guards) - len(walls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]  # 网格状态数组\n",
    "        q = deque([])  # 广度优先搜索队列\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                grid[nx][ny] = 1\n",
    "                q.append((nx, ny, k))\n",
    "        res = 0  # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0]*n for i in range(m)]\n",
    "        for i in walls:\n",
    "            x,y = i[0],i[1]\n",
    "            grid[x][y] = -2\n",
    "        \n",
    "        q = deque()\n",
    "        dx = [1,0,-1,0]\n",
    "        dy = [0,1,0,-1]\n",
    "        for i,j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                q.append((i,j,k))\n",
    "        \n",
    "        while q:\n",
    "            x,y,k = q.popleft()\n",
    "            nx,ny = x+dx[k],y+dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                grid[nx][ny] = 1\n",
    "                q.append((nx,ny,k))\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        # 带有状态的bfs\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        q = deque()\n",
    "        inx = [0, 0, 1, -1]\n",
    "        iny = [1, -1, 0, 0]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            dx, dy = x + inx[k], y + iny[k]\n",
    "            if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] >= 0:\n",
    "                if grid[dx][dy] & (1 << k) == 0:\n",
    "                    grid[dx][dy] |= 1 << k\n",
    "                    q.append((dx, dy, k))\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for  _ in range(m)]   # 网格状态数组\n",
    "        q = deque([])   # 广度优先搜索队列\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    # 对应状态未遍历过\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "        res = 0   # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for  _ in range(m)]   # 网格状态数组\n",
    "        q = deque([])   # 广度优先搜索队列\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    # 对应状态未遍历过\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "        res = 0   # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        q = deque([])\n",
    "        # 预处理\n",
    "        for x,y in guards:\n",
    "            grid[x][y] = -1\n",
    "            for k in range(4):\n",
    "                q.append((x,y,k))\n",
    "        for x,y in walls:\n",
    "            grid[x][y] = -2\n",
    "        \n",
    "        # BFS\n",
    "        dx = [1,-1,0,0]\n",
    "        dy = [0,0,1,-1]\n",
    "        while q:\n",
    "            x,y,k = q.popleft()\n",
    "            nx = x+dx[k]\n",
    "            ny = y+dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                if grid[nx][ny]&(1 << k) == 0:\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx,ny,k))\n",
    "        # 枚举每个格子\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "\n",
    "        q = deque([])\n",
    "\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    # 对应状态未遍历过\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "            \n",
    "        res = 0   # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]  # 网格状态数组\n",
    "        q = deque([])  # 广度优先搜索队列\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    # 对应状态未遍历过\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "        res = 0  # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        q = deque([])\n",
    "        # 预处理\n",
    "        for x,y in guards:\n",
    "            grid[x][y] = -1\n",
    "            for k in range(4):\n",
    "                q.append((x,y,k))\n",
    "        for x,y in walls:\n",
    "            grid[x][y] = -2\n",
    "        \n",
    "        # BFS\n",
    "        dx = [1,-1,0,0]\n",
    "        dy = [0,0,1,-1]\n",
    "        while q:\n",
    "            x,y,k = q.popleft()\n",
    "            nx = x+dx[k]\n",
    "            ny = y+dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                if (grid[nx][ny]>>k)&1 == 0:\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx,ny,k))\n",
    "        # 枚举每个格子\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        q = deque([])\n",
    "        # 预处理\n",
    "        for x,y in guards:\n",
    "            grid[x][y] = -1\n",
    "            for k in range(4):\n",
    "                q.append((x,y,k))\n",
    "        for x,y in walls:\n",
    "            grid[x][y] = -2\n",
    "        \n",
    "        # BFS\n",
    "        dx = [1,-1,0,0]\n",
    "        dy = [0,0,1,-1]\n",
    "        while q:\n",
    "            x,y,k = q.popleft()\n",
    "            nx = x+dx[k]\n",
    "            ny = y+dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                if (grid[nx][ny]>>k)&1 == 0:\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx,ny,k))\n",
    "        # 枚举每个格子\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for  _ in range(m)]   # 网格状态数组\n",
    "        q = deque([])   # 广度优先搜索队列\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                # 将四个方向视线对应的状态均添加进搜索队列中\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                # 沿着视线方向的下一个坐标合法，且不为警卫或墙\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    # 对应状态未遍历过\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "        res = 0   # 未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for  _ in range(m)]\n",
    "        q = deque([])\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i, j in guards:\n",
    "            grid[i][j] = -1\n",
    "            for k in range(4):\n",
    "                q.append((i, j, k))\n",
    "        for i, j in walls:\n",
    "            grid[i][j] = -2\n",
    "        while q:\n",
    "            x, y, k = q.popleft()\n",
    "            nx, ny = x + dx[k], y + dy[k]\n",
    "            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:\n",
    "                if grid[nx][ny] & (1 << k) == 0:\n",
    "                    grid[nx][ny] |= (1 << k)\n",
    "                    q.append((nx, ny, k))\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res += grid[i][j] == 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        #网格状态数组\n",
    "        grid=[[0]*n for _ in range(m)]\n",
    "        #广度优先队列\n",
    "        q=deque([])\n",
    "        # 每个方向的单位向量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i,j in guards:\n",
    "            #警卫对应的状态值为−1\n",
    "            grid[i][j]=-1\n",
    "            for k in range(4):\n",
    "                #将四个方向视线对应的状态添加进搜索队列中\n",
    "                #一个队列中的点只会对一个一个特定的方向 而不是四个方向\n",
    "                q.append((i,j,k))\n",
    "        \n",
    "        for i,j in walls:\n",
    "            #墙对应的状态值为−2\n",
    "            grid[i][j]=-2\n",
    "        \n",
    "        while q:\n",
    "            x,y,k=q.popleft()\n",
    "            nx,ny=x+dx[k],y+dy[k]\n",
    "            #未被保卫的格子对应的状态值为0  被保卫格子对应的状态值为正整数\n",
    "            if 0<=nx<m and 0<=ny<n and grid[nx][ny]>=0:\n",
    "                #从低到高的第k位为1代表有指向第k个方向的视线经过该点，反之则代表没有。\n",
    "                #对应方向没有遍历过\n",
    "                if grid[nx][ny]&(1<<k)==0:\n",
    "                    grid[nx][ny]|=(1<<k)\n",
    "                    #仍然继承的是上一个点的方向\n",
    "                    q.append((nx,ny,k))\n",
    "        \n",
    "        res=0#未被保护格子数目\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        res = m * n\n",
    "        g = [[False] * n for _ in range(m)]\n",
    "        w = [[False] * n for _ in range(m)]\n",
    "        unguarded = [[True] * n for _ in range(m)]\n",
    "        for r, c in guards:\n",
    "            g[r][c] = True\n",
    "            unguarded[r][c] = False\n",
    "            res -= 1\n",
    "        for r, c in walls:\n",
    "            w[r][c] = True\n",
    "            unguarded[r][c] = False\n",
    "            res -= 1\n",
    "        for r, c in guards:\n",
    "            for rr in reversed(range(r)):\n",
    "                if unguarded[rr][c]:\n",
    "                    res -= 1\n",
    "                    unguarded[rr][c] = False\n",
    "                if g[rr][c] or w[rr][c]:\n",
    "                    break\n",
    "            for rr in range(r + 1, m):\n",
    "                if unguarded[rr][c]:\n",
    "                    res -= 1\n",
    "                    unguarded[rr][c] = False\n",
    "                if g[rr][c] or w[rr][c]:\n",
    "                    break\n",
    "            for cc in reversed(range(c)):\n",
    "                if unguarded[r][cc]:\n",
    "                    res -= 1\n",
    "                    unguarded[r][cc] = False\n",
    "                if g[r][cc] or w[r][cc]:\n",
    "                    break\n",
    "            for cc in range(c + 1, n):\n",
    "                if unguarded[r][cc]:\n",
    "                    res -= 1\n",
    "                    unguarded[r][cc] = False\n",
    "                if g[r][cc] or w[r][cc]:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        mat = [[0] * n for _ in range(m)] \n",
    "        table = [[0] * n for _ in range(m)]\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        for x, y in guards:\n",
    "            mat[x][y] = 1\n",
    "            table[x][y] = 1\n",
    "            vis[x][y] = 1\n",
    "        for x, y in walls:\n",
    "            mat[x][y] = 1 \n",
    "            table[x][y] = 2\n",
    "            vis[x][y] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            st = []\n",
    "            for j in range(n-1, -1, -1):\n",
    "                while st and mat[i][st[-1]] < mat[i][j]:\n",
    "                    if table[i][j] == 1:\n",
    "                        vis[i][st[-1]] = 1\n",
    "                    st.pop()\n",
    "                st.append(j)\n",
    "            st = [] \n",
    "            for j in range(n):\n",
    "                while st and mat[i][st[-1]] < mat[i][j]:\n",
    "                    if table[i][j] == 1:\n",
    "                        vis[i][st[-1]] = 1\n",
    "                    st.pop()\n",
    "                st.append(j) \n",
    "        for j in range(n):\n",
    "            st = []\n",
    "            for i in range(m-1, -1, -1):\n",
    "                while st and mat[st[-1]][j] < mat[i][j]:\n",
    "                    if table[i][j] == 1:\n",
    "                        vis[st[-1]][j] = 1\n",
    "                    st.pop()\n",
    "                st.append(i) \n",
    "            st = []\n",
    "            for i in range(m):\n",
    "                while st and mat[st[-1]][j] < mat[i][j]:\n",
    "                    if table[i][j] == 1:\n",
    "                        vis[st[-1]][j] = 1\n",
    "                    st.pop()\n",
    "                st.append(i)     \n",
    "        ans = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans += 1 - vis[i][j]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, n: int, m: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        q=Counter()\n",
    "        ans=0\n",
    "        qq=Counter()\n",
    "        e=Counter()\n",
    "        for x in (walls):\n",
    "            q[(x[0],x[1])]+=1\n",
    "        for y in guards:\n",
    "            e[(y[0],y[1])]+=1    \n",
    "        def g(i,j):\n",
    "           nonlocal ans\n",
    "           for a,b in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "              c1=i+a\n",
    "              c2=j+b\n",
    "              while 0<=c1<n and 0<=c2<m and (c1,c2) not in q and (c1,c2) not in e:\n",
    "                  if qq[(c1,c2)]==0:\n",
    "                    qq[(c1,c2)]+=1\n",
    "                    ans+=1  \n",
    "                  c1+=a\n",
    "                  c2+=b\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "              if (i,j) in e:\n",
    "                 q[(i,j)]+=1\n",
    "                 g(i,j)\n",
    "        return m*n-len(guards)-len(walls)-ans                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        q=deque([])\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for x,y in guards:\n",
    "            grid[x][y]=-1\n",
    "            for k in range(4):\n",
    "                q.append([x,y,k])\n",
    "        \n",
    "        for x,y in walls:\n",
    "            grid[x][y]=-2\n",
    "        \n",
    "        while q:\n",
    "            x,y,k=q.popleft()\n",
    "            nx,ny=x+dx[k],y+dy[k]\n",
    "            if 0<=nx<m and 0<=ny<n and grid[nx][ny]>=0:\n",
    "                if grid[nx][ny]&(1<<k)==0:\n",
    "                    q.append([nx,ny,k])\n",
    "                    grid[nx][ny]|=(1<<k)\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        #0 unguarded, 1 guard, -1 wall, 2 guarded\n",
    "        q = deque()\n",
    "        grid = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for x, y in guards:\n",
    "            grid[x][y] = 1\n",
    "            q.append([x, y, 0, 1])\n",
    "            q.append([x, y, 0, -1])\n",
    "            q.append([x, y, 1, 0])\n",
    "            q.append([x, y, -1, 0])\n",
    "        for x, y in walls:\n",
    "            grid[x][y] = -1\n",
    "        def isEnd(x, y):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return True\n",
    "            if grid[x][y] == 1 or grid[x][y] == -1:\n",
    "                return True\n",
    "            return False\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                x, y, dx, dy = q.popleft()\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if not isEnd(new_x, new_y):\n",
    "                    grid[new_x][new_y] = 2\n",
    "                    q.append([new_x, new_y, dx, dy])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        # 2 <= m * n <= 10^5\n",
    "        # 横向一次多源bfs和纵向一次多源bfs就可以解决问题了\n",
    "        grid = [['N' for _ in range(n)] for _ in range(m)]\n",
    "        for x, y in guards:\n",
    "            grid[x][y] = 'G'\n",
    "        for x, y in walls:\n",
    "            grid[x][y] = 'W'\n",
    "            \n",
    "        vis = {tuple(g) for g in guards}\n",
    "        cur = [tuple(g) for g in guards]\n",
    "        \n",
    "        while cur:\n",
    "            nxt = set()\n",
    "            for x, y in cur:\n",
    "                for u, v in (x+1, y), (x-1, y):\n",
    "                    if 0 <= u < m and 0 <= v < n and grid[u][v] in 'NT' and (u, v) not in vis:\n",
    "                        grid[u][v] = 'T'\n",
    "                        vis.add((u, v))\n",
    "                        nxt.add((u, v))\n",
    "            cur = list(nxt)\n",
    "        \n",
    "        vis = {tuple(g) for g in guards}\n",
    "        cur = [tuple(g) for g in guards]\n",
    "        \n",
    "        while cur:\n",
    "            nxt = set()\n",
    "            for x, y in cur:\n",
    "                for u, v in (x, y+1), (x, y-1):\n",
    "                    if 0 <= u < m and 0 <= v < n and grid[u][v] in 'NT' and (u, v) not in vis:\n",
    "                        grid[u][v] = 'T'\n",
    "                        vis.add((u, v))\n",
    "                        nxt.add((u, v))\n",
    "            cur = list(nxt) \n",
    "        \n",
    "    \n",
    "        return sum([grid[i][j] == 'N' for i in range(m) for j in range(n)])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        \n",
    "        DIRS = set(['up', 'down', 'left', 'right'])\n",
    "        \n",
    "        deque = collections.deque()     # 双端队列\n",
    "        \n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        for i,j in walls:\n",
    "            grid[i][j] = 'W'    # 墙\n",
    "        for i,j in guards:      \n",
    "            grid[i][j] = 'G'    # 警卫\n",
    "            for d in DIRS:\n",
    "                deque.append((i,j,d))   # 从警卫开始BFS\n",
    "        \n",
    "        visited = set()\n",
    "        while deque:\n",
    "            i, j, d = deque.popleft()\n",
    "            if d=='up':                 # 判断方向【不改变BFS行进方向】\n",
    "                i -= 1\n",
    "            elif d=='down':\n",
    "                i += 1\n",
    "            elif d=='left':\n",
    "                j -= 1\n",
    "            elif d=='right':\n",
    "                j += 1\n",
    "            \n",
    "            if i<0 or i>=m or j<0 or j>=n or grid[i][j] in ['W', 'G'] or (i,j, d) in visited:\n",
    "                continue\n",
    "            \n",
    "            grid[i][j] = 1\n",
    "            visited.add((i,j,d))        # visited需记录行进方向\n",
    "            deque.append((i,j,d))       # 入列【不改变BFS行进方向】\n",
    "        \n",
    "        ans = sum(grid[i][j] == 0 for i in range(m) for j in range(n))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        encodeFn = lambda r,c: r*n+c\n",
    "        visited = set(encodeFn(r, c) for r, c in chain(guards, walls))\n",
    "        stops = set(visited)\n",
    "        q = deque((r,c,_dir) for r, c in guards for _dir in range(4))\n",
    "        delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        while q:\n",
    "            r, c, _dir = q.popleft()\n",
    "            nr, nc = r + delta[_dir][0], c + delta[_dir][1]\n",
    "            if nr < 0 or nr == m or nc < 0 or nc == n: continue\n",
    "            v = encodeFn(nr, nc)\n",
    "            if v in stops: continue\n",
    "            visited.add(v)\n",
    "            q.append((nr, nc, _dir))\n",
    "        return m*n - len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:\n",
    "        d=[(1,0),(0,1),(0,-1),(-1,0)]\n",
    "        grid=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        for a,b in walls:\n",
    "            grid[a][b]=-1\n",
    "        guards.sort()\n",
    "        s=set()\n",
    "        for a,b in guards:\n",
    "            grid[a][b]=2\n",
    "            for da,db in d:\n",
    "                x,y=a,b\n",
    "                while 0<=x<m and 0<=y<n and grid[x][y]!=-1:\n",
    "                    if (x,y,da,db)in s:\n",
    "                        break\n",
    "                    s.add((x,y,da,db))\n",
    "                    grid[x][y]=1\n",
    "                    x+=da \n",
    "                    y+=db\n",
    "        ret=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    ret+=1\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
